//找出数组中重复的数字。 
//
// 
//在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请
//找出数组中任意一个重复的数字。 
//
// 示例 1： 
//
// 输入：
//[2, 3, 1, 0, 2, 5, 3]
//输出：2 或 3 
// 
//
// 
//
// 限制： 
//
// 2 <= n <= 100000 
// Related Topics 数组 哈希表 
// 👍 334 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findRepeatNumber(int[] nums) {
        // 第一种方法，哈希表
//        Set<Integer> set = new HashSet<Integer>();
//        for (int num :
//                nums) {
//            if (!set.add(num)){
//                return num;
//            }
//        }
//        return -1;

        // 第二种方法，根据题意得知可以将数字和下标对应上，如果已存在值说明重复，返回即可
        int length = nums.length;
        for (int i = 0; i < length; i++){
            while (nums[i] != i && nums[nums[i]] != nums[i]){
                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
            if (nums[i] != i && nums[nums[i]] == nums[i]){
                return nums[i];
            }
        }
        return -1;
    }

}
//leetcode submit region end(Prohibit modification and deletion)
